package com.monkeyboy.tree;

import com.monkeyboy.TreeNode;

import java.util.ArrayList;

/**
 * 题目：
 * 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * <p>
 * 解题思路：
 * 注意审题完整的一条路径是从根节点到叶子节点，所以代码中的路径终止判断条件就是节点的左节点和右节点都
 * 为null的时候才算一条完整的路径
 *
 * @Author Gavin
 * @date 2021.04.20 15:39
 */
public class Tree08 {
    public static ArrayList<ArrayList<Integer>> paths = new ArrayList<>();

    public static ArrayList<ArrayList<Integer>> getPaths(TreeNode root, Integer target) {
        if (root == null) {
            return null;
        }
        if (root.val > target) {
            return null;
        }
        solution(root, new ArrayList<>(), target);
        return paths;
    }

    public static void solution(TreeNode root, ArrayList<Integer> path, Integer target) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            paths.add(path);
        } else {
            solution(root.left, path, target);
            solution(root.right, path, target);
        }
        //这里移除是比较混的一点，这里是表示一个根节点是有两个左右节点的，如果计算了左边的路径后还要计算右边
        //的和的话就需要先把左边的移除掉
        path.remove(path.size()-1);
    }
}
